{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 汉诺塔问题\n",
    "- 规则：\n",
    "    1. 每次移动一个盘子\n",
    "    2. 任何时候大盘子在下面，小盘子在上面\n",
    "- 方法：\n",
    "    1. n=1： 直接把A上的一个盘子移动到C上， A->C\n",
    "    2. n=2: \n",
    "        1. 把小盘子从A放到B上， A->B\n",
    "        2. 把大盘子从A放到C上， A->C\n",
    "        3. 把小盘子从B放到C上， B->C\n",
    "    3. n=3: \n",
    "        1. 把A上的两个盘子，通过C移动到B上去， 调用递归实现\n",
    "        2. 把A上剩下的一个最大盘子移动到C上， A->C\n",
    "        3. 把B上两个盘子，借助于A，挪到C上去， 调用递归\n",
    "    4. n = n：\n",
    "        1. 把A上的n-1个盘子，借助于C，移动到B上去，调用递归\n",
    "        2. 把A上的最大盘子，也是唯一一个，移动到C上，A->C\n",
    "        3. 把B上n-1个盘子，借助于A，移动到C上， 调用递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> C\n"
     ]
    }
   ],
   "source": [
    "def hano(n, a, b, c):\n",
    "    '''\n",
    "    汉诺塔的递归实现\n",
    "    n：代表几个盘子\n",
    "    a：代表第一个塔，开始的塔\n",
    "    b：代表第二个塔，中间过渡的塔\n",
    "    c：代表第三个塔, 目标塔\n",
    "    '''\n",
    "    if n == 1:\n",
    "        print(a, \"-->\", c)\n",
    "        return None\n",
    "    '''\n",
    "    \n",
    "    if n == 2:\n",
    "        print(a, \"-->\", b)\n",
    "        print(a, \"-->\", c)\n",
    "        print(b, \"-->\", c)\n",
    "        return None\n",
    "    '''\n",
    "    # 把n-1个盘子，从a塔借助于c塔，挪到b塔上去\n",
    "    hano(n-1, a, c, b)\n",
    "    print(a, \"-->\", c)\n",
    "    # 把n-1个盘子，从b塔，借助于a塔，挪到c塔上去\n",
    "    hano(n-1,b, a, c)\n",
    "    \n",
    "a = \"A\"\n",
    "b = \"B\"\n",
    "c = \"C\"\n",
    "\n",
    "n = 1\n",
    "hano(n, a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> B\n",
      "A --> C\n",
      "B --> C\n"
     ]
    }
   ],
   "source": [
    "n = 2\n",
    "hano(n, a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "A --> C\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n"
     ]
    }
   ],
   "source": [
    "n = 3\n",
    "hano(n, a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "A --> C\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "C --> A\n",
      "B --> A\n",
      "C --> B\n",
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "A --> C\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n",
      "B --> A\n",
      "C --> B\n",
      "C --> A\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n",
      "A --> B\n",
      "C --> B\n",
      "A --> C\n",
      "B --> A\n",
      "B --> C\n",
      "A --> C\n"
     ]
    }
   ],
   "source": [
    "n = 5\n",
    "hano(n, a, b, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List(列表）\n",
    "- del: 删除命令"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "# del 删除\n",
    "a = [1,2,3,4,5,6]\n",
    "del a[2]\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "140246810905416\n",
      "140246810905416\n",
      "[1, 2, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "# del 删除\n",
    "# 如果使用del之后，id的值和删除前不一样，则说明删除生成了一个新的list\n",
    "a = [1,2,3,4,5,6]\n",
    "print(id(a))\n",
    "del a[2]\n",
    "print(id(a))\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'a' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-94bf5611738e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdel\u001b[0m  \u001b[0ma\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'a' is not defined"
     ]
    }
   ],
   "source": [
    "# del一个变量后不能在继续使用此变量\n",
    "del  a\n",
    "print(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 'a', 'b', 'c']\n"
     ]
    }
   ],
   "source": [
    "# 使用加号链接两个列表\n",
    "a = [1,2,3,4,5]\n",
    "b = [5,6,7,8,9]\n",
    "d = ['a', 'b', 'c']\n",
    "c = a + b + d\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "# 使用乘号操作列表\n",
    "# 列表直接跟一个整数相乘 \n",
    "# 相当于把n个列表接在一起\n",
    "a = [1,2,3,4,5]\n",
    "b = a *3\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# 成员资格运算\n",
    "# 就是判断一个元素是否在爱list里边\n",
    "a = [1,2,3,4,5,6]\n",
    "b = 8\n",
    "\n",
    "#c 的值是一个布尔值\n",
    "c = b in a\n",
    "print(c)\n",
    "\n",
    "b = 4\n",
    "print(b in a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# not in \n",
    "a = [1,2,3,4,5]\n",
    "b = 9\n",
    "\n",
    "print(b not in a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 链表的遍历\n",
    "- for\n",
    "- while"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "# for in list\n",
    "a = [1,2,3,4,5]\n",
    "\n",
    "# 挨个打印a里边的元素\n",
    "for i in a:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# java， c++ 程序员写的python代码是这样的\n",
    "for i in range(0,len(a)):\n",
    "    print(a[i])\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I love wangxiaojing\n"
     ]
    }
   ],
   "source": [
    "b = [\"I love wangxiaojing\"]\n",
    "\n",
    "for i in b:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "<class 'range'>\n"
     ]
    }
   ],
   "source": [
    "# range\n",
    "# in 后面的变量要求是可以可迭代的内容\n",
    "for i in range(1,10):\n",
    "    print(i)\n",
    "\n",
    "print(type(range(1,10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# while循环访问list\n",
    "# 一般不用while遍历list\n",
    "\n",
    "a = [1,2,3,4,5,6]\n",
    "length = len(a)\n",
    "# indx表示的是list的下标\n",
    "indx = 0\n",
    "while indx < length:\n",
    "    print(a[indx])\n",
    "    indx += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one -- 1\n",
      "two -- 2\n",
      "three -- 3\n"
     ]
    }
   ],
   "source": [
    "# 双层列表循环\n",
    "\n",
    "#a 为嵌套列表，或者叫双层列表\n",
    "a = [[\"one\", 1], [\"two\", 2], [\"three\", 3] ]\n",
    "\n",
    "for k,v in a:\n",
    "    print(k, \"--\", v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "too many values to unpack (expected 2)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-29-a8afd4d727f2>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0ma\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"one\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"eins\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m\"two\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m\"three\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m8\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0;32mfor\u001b[0m \u001b[0mk\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0ma\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"--\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mv\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: too many values to unpack (expected 2)"
     ]
    }
   ],
   "source": [
    "# 双层列表循环变异\n",
    "\n",
    "#a 为嵌套列表，或者叫双层列表\n",
    "a = [[\"one\", 1, \"eins\"], [\"two\", 2], [\"three\", 3,4,5,6,8] ]\n",
    "\n",
    "for k,v in a:\n",
    "    print(k, \"--\", v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one -- 1 -- eins\n",
      "two -- 2 -- zwei\n",
      "three -- 3 -- drei\n"
     ]
    }
   ],
   "source": [
    "# 双层列表循环变异\n",
    "\n",
    "#a 为嵌套列表，或者叫双层列表\n",
    "a = [[\"one\", 1, \"eins\"], [\"two\", 2,\"zwei\"], [\"three\", 3,\"drei\"] ]\n",
    "#这个例子说明，k，v,w的个数应该跟解包出来的变量个数一致\n",
    "for k,v,w in a:\n",
    "    print(k, \"--\", v, \"--\",w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 列表内涵: list content\n",
    "- 通过简单方法创作列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'c']\n"
     ]
    }
   ],
   "source": [
    "# for 创建\n",
    "a = ['a', 'b', 'c']\n",
    "# 用list a创建一个list b\n",
    "# 下面代码的含义是，对于所有a中的元素，逐个放入新列表b中\n",
    "b = [i for i in a]\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 20, 30, 40, 50]\n"
     ]
    }
   ],
   "source": [
    "# 对a中所有元素乘以10，生成一个新list\n",
    "a = [1,2,3,4,5]\n",
    "# 用list a创建一个list b\n",
    "# 下面代码的含义是，对于所有a中的元素，逐个放入新列表b中\n",
    "b = [i*10 for i in a]\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34]\n"
     ]
    }
   ],
   "source": [
    "# 还可以过滤原来list中的内容病放入新列表\n",
    "# 比如原有列表a， 需要把所有a中的偶数生成新的列表b\n",
    "\n",
    "a = [x for x in range(1,35)] #生成从1到34的一个列表\n",
    "# 把a中所有偶数生成一个新的列表 b\n",
    "b = [m for m in a if m % 2 == 0]\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[100, 200, 300]\n",
      "[101, 201, 301, 102, 202, 302, 103, 203, 303]\n",
      "101  201  301  102  202  302  103  203  303  \n",
      "[101, 201, 102, 202, 103, 203]\n"
     ]
    }
   ],
   "source": [
    "# 列表生成式可以嵌套\n",
    "# 由两个列表a，b\n",
    "a = [i for i in range(1,4)] # 生成list a\n",
    "print(a)\n",
    "\n",
    "b = [i for i in range(100,400) if i % 100 == 0]\n",
    "print(b)\n",
    "\n",
    "# 列表生成是可以嵌套,此时等于两个for循环嵌套\n",
    "c = [  m+n for m in a for n in b]\n",
    "print(c)\n",
    "\n",
    "# 上面代码跟下面代码等价\n",
    "for m in a:\n",
    "    for n in b:\n",
    "        print(m+n, end=\"  \")\n",
    "print()\n",
    "\n",
    "\n",
    "\n",
    "# 嵌套的列表生城市也可以用条件表达式\n",
    "c = [  m+n for m in a for n in b if m+n < 250]\n",
    "print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关于列表的常用函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99\n",
      "99\n",
      "python\n"
     ]
    }
   ],
   "source": [
    "# len:求列表长度\n",
    "a = [x for x in range(1,100)]\n",
    "print(len(a))\n",
    "\n",
    "# max:求列表中的最大值\n",
    "# min： 同理\n",
    "print(max(a))\n",
    "\n",
    "b = ['man', 'film', 'python']\n",
    "print(max(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "# list：将其他格式的数据转换成list\n",
    "a = [1,2,3]\n",
    "print(list(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['I', ' ', 'l', 'o', 'v', 'e', ' ', 'w', 'a', 'n', 'g', 'x', 'i', 'a', 'o', 'j', 'i', 'n', 'g']\n"
     ]
    }
   ],
   "source": [
    "s = \"I love wangxiaojing\"\n",
    "print(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 13, 14, 15, 16, 17, 18]\n"
     ]
    }
   ],
   "source": [
    "# 把range产生的内容转换成list\n",
    "print(list(range(12, 19)))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
